from LeetCoder import *


# s = "leetscode", dictionary = ["leet","code","leetcode"]
class Solution:

    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        n = len(s)
        dp = [inf] * (n + 1)
        st = set(dictionary)
        dp[0] = 0
        for i in range(1, n + 1):
            dp[i] = i
            for j in range(i, -1, -1):
                for k in range(1, j + 1):
                    if s[k - 1:j:] in st:
                        dp[i] = min(dp[i], dp[k - 1] + i - j)
        return dp[n]


s = Solution()
print(
    s.minExtraChar("dwmodizxvvbosxxw", [
        "ox", "lb", "diz", "gu", "v", "ksv", "o", "nuq", "r", "txhe", "e",
        "wmo", "cehy", "tskz", "ds", "kzbu"
    ]))
print(s.minExtraChar(s="leetscode", dictionary=["leet", "code", "leetcode"]))
print(s.minExtraChar(s="sayhelloworld", dictionary=["hello", "world"]))
